# -*- coding: utf-8 -*-

''' Autor: Neuza Figueira - n.º 6036 '''

import sys
from random import uniform
from time import clock
import math
import matplotlib.pyplot as plt

class MergeSort():
        ''' Class to handle Merge sort implementation and testing.'''
        
        def merge_sort(self, A, p, r):
                '''Python Implementation of Merge sort.'''
                '''@param A -> List to sort.'''
                '''@param p -> First position of the sublist.'''
                '''@param r -> Last position of the sublist.'''
                if p < r:
                        q = (p + r) / 2
                        self.merge_sort(A, p, q)
                        self.merge_sort(A, q + 1, r)
                        self.merge(A, p, q, r)
                        pass
                return A
                pass


        def merge(self, A, p, q, r):
                '''Merge sort subroutine.'''
                '''@param A -> List to sort.'''
                '''@param p -> First position of the sublist.'''
                '''@param q -> Position to split the list in two.'''
                '''@param r -> Last position of the sublist.'''
                n1 = q - p + 1
                n2 = r - q

                L = [0 for k in range(n1 + 1)]
                R = [0 for k in range(n2 + 1)]

                for i in range(0, n1):
                        L[i] = A[p + i]
                        pass

                for j in range(0, n2):
                        R[j] = A[q + j + 1]
                        pass

                L[n1] = sys.maxint
                R[n2] = sys.maxint

                i = 0
                j = 0

                for k in range(p, r + 1):
                        if L[i] <= R[j]:
                                A[k] = L[i]
                                i = i + 1
                                pass
                        else:
                                A[k] = R[j]
                                j = j + 1
                        pass
                pass


        def testMergeSort(self):
                '''Testing the complexity of Merge sort.'''
                Z = range(50, 1050, 50)
                T = []
                M = 50
                for n in Z:
                        A = [ uniform(0.0, 1.0) for k in xrange(n)]
                        tempos = []
                        for k in range(M):
                            t1 = clock()
                            self.merge_sort(A, 0, len(A) - 1)
                            t2 = clock()
                            tempos.append(t2-t1)
                        media = reduce(lambda x, y: x + y, tempos) / len(tempos)
                        var = reduce(lambda x, y: x + (y-media)**2, [0] + tempos) / len(tempos)

                        T.append((n,media, var))

                X = [n for n, media, var in T]
                Y = [media for n, media, var in T]
                ct = 50e4
                Z = [(n * math.log(n)) / ct for n, media, var in T]

                plt.grid(True)
                plt.ylabel(u'T(n) - tempo de execução médio em segundos')
                plt.xlabel(u'n - número de elementos')
                plt.plot(X,Y,'rs', label="resultado experimental")
                plt.plot(X, Z, 'b^', label=u"previsão teórica")
                plt.legend()
                plt.show()
                pass


